/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */

var movingCount = function (m, n, k) {
    // 初始化数组
    let arr = new Array(m).fill(0)
    for (let i = 0; i < m; i++) {
        arr[i] = new Array(n).fill(0)
    }
    return dfs(0, 0, k, arr)

    function dfs(x, y, k, arr) {
        let i = x
        let j = y
        // 越界了说明不行
        if (x < 0 || x >= m || y < 0 || y >= n || arr[x][y] === 1) {
            return 0
        }
        else {
            let aSum = 0
            let bSum = 0
            while (i) {
                let temp = i % 10
                i = Math.floor(i / 10)
                aSum += temp
            }
            while (j) {
                let temp = j % 10
                j = Math.floor(j / 10)
                bSum += temp
            }
            // 坐标数位和大于k
            if (aSum + bSum > k) {
                return 0
            }
            else {
                arr[x][y] = 1
                return dfs(x + 1, y, k, arr) +
                    dfs(x, y + 1, k, arr) +
                    dfs(x - 1, y, k, arr) +
                    dfs(x, y - 1, k, arr) + 1
            }
        }
    }
};
console.log(movingCount(2, 3, 1))